import java.util.Arrays;

public class Solution16 {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int res;
        res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int sum = nums[i] + nums[i + 1] + nums[i + 2] - target;
            if (sum > 0 && sum > Math.abs(res)) {
                break;
            }
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int k = nums[i] + nums[left] + nums[right] - target;
                if (Math.abs(k) < Math.abs(res - target)) {
                    res = k + target;
                }
                if (k < 0) {
                    left++;
                } else if (k > 0) {
                    right--;
                } else {
                    return res;
                }
            }
            while (i < nums.length - 3 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return res;
    }
}
